1. Field of the Invention
This invention relates generally to iterative turbo decoding, and more particularly to adaptive halting algorithms that reduce computational complexity of iterative turbo decoders.
2. Description of the Prior Art
Turbo code is well known computational tool that was proposed in 1993 and that attracted the attention of researchers and developers, especially in the art of communication engineering. C. Berrou, A. Glavieux, and P. Thitimajshima, Near Shannon Limit Error-correcting Coding and Decoding: Turbo Codes (I), Proc.ICC ""93, pp. 1064-1070, May 1993. The Berrou et al. reference is incorporated by reference herein. A turbo encoder is composed of two recursive systematic convolutional (RSC) encoders and an interleaver to generate the interleaved version of an input information sequence. The interleaved sequence is also encoded using one of the RSC encoders. The resultant turbo code, using parallel concatenation of the two RSC codes, has a substantially large free Hamming distance and therefore provides a powerful error correcting code. The aforesaid Hamming distance can be further improved by employing long interleavers a the expense of larger memory capacity.
FIG. 4 is a simplified block diagram of a parallel-concatenated rate 1/3 turbo encoder. A parallel-concatenated turbo encoder has two or more component encoders in conjunction with one or more interleavers. A component encoder C1 to create a parity sequence X1 encodes an input information sequence. The input information sequence is interleaved and then encoded by C2 to create a second parity sequence X2. The information sequence and two parity sequences are then multiplexed to create a coded sequence.
The foregoing two RSC codes are alternately MAP-decoded in the turbo decoder, and the reliability of the soft output of the MAP decoder is iteratively updated. The sign of the soft output is improved as a decoded output following a sufficient number of iteration steps. The amplitude of the soft output gradually increases during the iteration process. However, the sign generally remains constant after several iteration steps. Thus, it is easy to recognize a decoded output can become error-free in just a few iteration steps for low-noise channels having a channel-decoded bit error rate (BER) as low as 10xe2x88x926. Detection of an error-free decoded sequence can significantly reduce computational complexity since the iteration process can then be halted without requiring further iteration computations.
A transmitted sequence is generally encoded with an error detection code such as the familiar cyclic redundancy check (CRC) code disclosed by S. Lin and D. J. Costello Jr., Error Control Coding: Fundamentals and Applications, Prentice Hall, New Jersey, 1983, and incorporated herein by reference. The above error-free decoding can then be checked for accuracy at the receiver side using the CRC code; and when error-free decoding is detected during an iteration, the remaining portion of the iteration can either be ignored or completely halted. A. Shibutani, H. Suda, and F. Adachi, Decoding-complexity Reduction On Turbo-CRC Concatenated Code in W-CDMA Mobile Radio, Proc. IEICE General Conf., B-5-109, vol. 1, pp. 541, March 1999 (in Japanese), and incorporated by reference herein, have shown the effectiveness of the foregoing iterative turbo decoding process.
If a transmitted sequence is not encoded with the CRC code, the foregoing technique of Shibutani et al. cannot be applied however. Even if the transmitted sequence is encoded with the CRC code, the associated receiver decoder must a priori know the generator polynomial of the CRC code and the position of its redundancy check words in the received sequence. This limitation makes the design of the decoder complicated for variable rate data communications.
In J. Hagenauer, E. Offer, and L. Papke, Iterative Decoding of Binary Block and Convolutional Codes, IEEE Trans. Inf. Theory, vol. 42, pp. 429-445, March 1996 and in U.S. Pat. No. 5,761,248, entitled Method and Arrangement for Determining an Adaptive Abort Criterion in Iterative Decoding of Multi-dimensionally Coded Information, by J. Hagenauer and F. Burkert, issued June 1998, both references incorporated herein by reference, Hagenauer et al. have shown implementation of the adaptive halting algorithm without resorting to use of the transmitted CRC code. The adaptive halting algorithm of Hagenauer et al. makes use of the difference sequence between two soft output sequences determined at the iteration step as well as the preceding iteration step and derived at each iteration step. Then the L2 norm of the difference sequence (cross entropy of the two soft output sequences) is calculated at each iteration step. Once the cross entropy of the two soft output sequences becomes less than a predetermined threshold value, the iteration process is halted. Although the techniques developed by Hagenauer et al. do not require use of the transmitted CRC code, the technique otherwise requires an extra large memory capacity to store the soft output sequence data at each preceding iteration step. This is so since the soft output sequence of a typical turbo decoder is very long and therefore has soft output symbols with long word lengths. Further, the aforementioned cross entropy needs to be computed using high accuracy in order to accurately detect the convergence of iterative decoding, which significantly increases the hardware size of the multiplier used for the calculation of the L2 norm.
P. Robertson, Illuminating the Structure of Parallel Concatenated Recursive Systematic (TURBO) Codes, Proc. GLOBECOM""94, pp. 1298-1303, November 1994, incorporated by reference herein, proposes application of the adaptive halting algorithm using the variance of the soft output sequence as the halting criterion. Although the Robertson technique does not require an extra large memory capacity or a large multiplier such as required when using the foregoing cross entropy computation methods, the technique of Robertson nonetheless requires a multiplier to calculate the variance. The requirement for a multiplier is disadvantageous for low power and low-cost silicon implementations since the additional hardware will increase both the size and power requirements necessary to implement the adaptive halting algorithm.
In view of the foregoing, a need exists in the communication art for an adaptive halting structure and method that does not require use of the passively embedded CRC code and that does not require surplusage multipliers or memory capacity.
The present invention is directed to a structure and method of implementing an adaptive halting algorithm (CRC-based comparison algorithm) associated with iterative turbo decoding without resorting to use of a passively included CRC code in the transmitted information sequence. As used herein, CRC means cyclic redundancy check. The soft output sequence observed at each iteration step contains information on three L-valued sequences; the channel information sequence, the a priori information sequence and the extrinsic information sequence. The channel information sequence is constant during the iteration and thus does not have any information on the state of the convergence necessary to halt the iteration process. Thus, the change of the sum of the a priori information sequence and the extrinsic information sequence is observed during each iteration step. The soft output sequence containing the channel information sequence is, however, referred to in order to estimate the state of the convergence, such as disclosed by Hagenauer et al. above. The sum of the a priori information sequence and the extrinsic information sequence contains accurate information on the state of the convergence and thus is quantized into a binary sequence. During an iteration, any changes of the binary sequence are detected. The iteration process is halted once this change can no longer be detected. The foregoing detection at each iteration step can be easily implemented by using a CRC code defined only at the decoder, which does not seriously increase the hardware size of the decoder.
The present iterative turbo decoding process utilizing the CRC-based comparison algorithm is implemented by further dividing each iteration step into two stages. MAP-decoding is performed at each stage of the iteration step. The MAP-decoding produces informative sequences at each stage that are then subsequently summed and quantized into binary sequences (reference sequences). The pair of reference sequences is compared with the respective pair of reference sequences generated in the previous iteration step. The iteration process is then halted only if the reference sequences at the first and the second stages of the iteration step correspond identically with those same reference sequences generated at the preceding iteration step. Using a CRC code defined by the decoder makes the comparison.
As used herein, the following words have the following meanings. The words xe2x80x9calgorithmic softwarexe2x80x9d mean an algorithmic program used to direct the processing of data by a computer or data processing device. The words xe2x80x9cdata processing devicexe2x80x9d as used herein refer to a CPU, DSP, microprocessor, micro-controller, or other like device and an interface system. The interface system provides access to the data processing device such that data could be entered and processed by the data processing device. The words xe2x80x9cdiscrete dataxe2x80x9d as used herein are interchangeable with xe2x80x9cdigitized dataxe2x80x9d and xe2x80x9cdigitized dataxe2x80x9d as used herein means data which are stored in the form of singularly isolated, discontinuous data or digits. The word xe2x80x9cinterleaverxe2x80x9d as used herein means a single input, single output device that takes sequences of symbols in a fixed alphabet and produces an output sequence of the identical symbols over the same alphabet in a different temporal order. Then for an input sequence xi, ixcex5Z to an interleaver, the output sequence yi, ixcex5Z can be written as yi=xxcfx80(i), where xcfx80 is defined as an invertible function: xcfx80:Zxe2x86x92Z.
In one aspect of the invention, a method and associated structure are implemented to provide a CRC-based adaptive halting algorithm associated with iterative turbo decoding to more efficiently estimate the state of the convergence for a variable rate data communication signal.
In still another aspect of the invention, a method and associated structure are implemented to provide a CRC-based adaptive halting algorithm associated with iterative turbo decoding to estimate the state of the convergence of received communication signals devoid of passively embedded error detection, e.g. CRC, codes.
In yet another aspect of the invention, a method and associated structure are provided to implement a CRC-based adaptive halting algorithm associated with iterative turbo decoding to estimate the state of the convergence of a data communication signal without the necessity of direct reference to soft output sequences.
In another aspect of the invention, a method and associated structure are provided to implement a CRC-based adaptive halting algorithm associated with iterative turbo decoding to estimate the state of the convergence of a data communication signal without requiring either a large memory capacity or a multiplier with a long word length.
Another aspect of the invention is associated with a CRC-based adaptive halting algorithm iterative turbo decoding procedure and structure in which the computational complexity of the decoder(s) can be reduced by about 50% over known iterative turbo decoder structures without degradation in the BER and FER, to estimate the state of the convergence of a data communication signal.
Still another aspect of the invention is associated with a CRC-based adaptive halting algorithm iterative turbo decoding procedure and structure in which the hardware sizes of the CRC decoder(s), the comparator(s) and the register(s) are insignificant in comparison with those of the MAP decoder(s) and the interleaver(s) of known turbo decoders.